﻿using System;
using System.Diagnostics.Contracts;

namespace O1
{
    [ContractVerification(true)]
    internal static class PrimeExtensions
    {
        public const int MaxPrime = 0x7FEFFFFD;
        
        private const int PrimeMod = 101;

        private static readonly int[] CommonPrimes = 
        {
            3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
            1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
            17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
            187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
            1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369
        };

        public static int RoundToPositivePrime(this int value)
        {
            Contract.Requires(value <= MaxPrime);
            Contract.Ensures(Contract.Result<int>() >= 3);
            Contract.Ensures(Contract.Result<int>() >= value);
            Contract.Assume(Contract.Result<int>() <= MaxPrime);

            if (value < 3)
            {
                return 3;
            }

            if (value >= MaxPrime)
            {
                return MaxPrime;
            }

            Contract.Assume(CommonPrimes.Length > 1);
            if (value > CommonPrimes[CommonPrimes.Length - 1])
            {
                for (int i = value | 1; i < int.MaxValue; i += 2)
                {
                    if (IsPrime(i) && ((i - 1) % PrimeMod != 0))
                    {
                        return Math.Min(i, MaxPrime);
                    }
                }
            }

            for (int i = 0; i < CommonPrimes.Length; i++)
            {
                int prime = CommonPrimes[i];
                if (prime >= value)
                {
                    return prime;
                }
            }

            return value;
        }

        public static int RoundToPositivePrime(this int value, float factor)
        {
            Contract.Requires(1 < factor);
            Contract.Requires(value <= MaxPrime);
            Contract.Requires(((int)(factor * (float)value)) <= MaxPrime || MaxPrime > value);
            Contract.Ensures(Contract.Result<int>() >= value);

            var newSize = (int)(factor * value);
            if ((uint)newSize >= MaxPrime)
            {
                return MaxPrime;
            }

            Contract.Assume(value < newSize);

            return RoundToPositivePrime(newSize);
        }

        public static bool IsPrime(this int value)
        {
            if ((value & 1) != 0)
            {
                int limit = (int)Math.Sqrt(value);
                for (int divisor = 3; divisor <= limit; divisor += 2)
                {
                    if ((value % divisor) == 0)
                    {
                        return false;
                    }
                }

                return true;
            }

            return value == 2;
        }
    }
}